The invention relates to a method for carrying out a search for possible destinations by means of a navigation system of a motor vehicle. The invention furthermore relates to a navigation system and a motor vehicle with a navigation system, wherein the navigation system is designed to carry out a method of this type.
Navigation systems for motor vehicles are already known from the prior art and serve to output navigation instructions which support the driver in guiding the motor vehicle to a specific destination. Interest is focused here on the performance of a search for possible navigation destinations in a navigation database of a navigation system. In this context, it is already known, for example, that the required navigation destination can be found via a hierarchical destination input. Here, the user must first enter the country and the required town or the zip code in order then to be able to define the required street and house number more specifically. Furthermore, navigation systems are also known in which navigation destinations can be found by means of a full-text search using a character string that is as unambiguous as possible. A full-text search of this type is particularly user-friendly and enables the required destination to be found with only a single destination input.
A navigation system is known from DE 10 2006 057 921 A1 in which a list of possible navigation destinations is proposed on the basis of a combination of letters entered by the user. After each input of a character or group of characters, a search is already carried out in a database on the basis of the partial input entered so far by the user. A search unit provided for this search can carry out a free-text search or a full-text search in the database on the basis of a full-text index. The search can be restricted to navigation destinations that are located within a predetermined radius around the current position of the navigation device.
DE 10 2010 005 502 A1 describes a method for carrying out a search in an infotainment system of a motor vehicle, wherein the infotainment system has a plurality of functionalities that can be invoked by actuating one of the fixed-function operating elements assigned to the respective functionality. A search for folders, files or data content is performed in a predetermined search field on the basis of an alphanumeric input of a user, and the search results are displayed on a display device for this predetermined search field. If the actuation of a fixed-function operating element is then detected, the search field is modified on the basis of the actuation, and new search results for this new search field are displayed.
A method for carrying out a full-text search in a database of a navigation system is furthermore known from EP 2 354 984 A1. In order to be able to design the full-text search in a less complex manner, a plurality of index tables are used which are interlinked via a higher-order table. Along with the actual, unique object designations for navigation destinations, a single database entry can also contain category data indicating, for example, that a specific navigation destination is a restaurant.
The fact that databases of navigation systems have a relatively complex structure and are therefore relatively large can be regarded as a disadvantage of the known navigation systems. This, in turn, has the effect that the performance of the search can take a very long time overall, since the entire database must be searched in each case in a complex manner for the required destination. Furthermore, a correspondingly large main memory into which the database must be loaded during the search is required for the processing of the large navigation database. However, main memories of this type are available to only a limited extent, particularly in motor vehicles.
The object of the invention is to provide a way in which, in a method of the aforementioned type, processing and/or data complexity can be reduced compared with the prior art during the search for possible destinations.
This and other objects are achieved by a method, by a navigation system and by a motor vehicle according to embodiments of the invention.
A method according to the invention serves to operate a navigation system of a motor vehicle for a search for possible destinations. The navigation system contains a first and a second database. Database entries indicating the geographical regions or areas are stored in the first database. In contrast, database entries indicating street names and/or special destinations are stored in the second database, wherein a reference to at least one geographical region from the first database is indicated in the second database in addition to each street name and/or special destination. A search input which a user performs with an input device is received by way of a processing device of the navigation system. The first database is then searched for matching database entries by way of the processing device depending on the search input, and a first results list of matching database entries is provided here. Independently therefrom, the second database is also searched for matching database entries depending on the same search input, and a second results list of matching entries is provided here. The database entries from the second results list are then allocated to the database entries from the first results list using the references. The database entries from the second results list are allocated in each case to the database entry from the first results list to which the respective reference refers. Entry pairs are thus determined, which in each case contain a database entry from the first results list and a database entry from the second results list. A selection list comprising the entry pairs as the possible destinations is then displayed on a display device so that the user can select one of the displayed destinations. If a specific destination is selected, the processing device calculates a corresponding navigation route via which the motor vehicle can be guided to the selected destination.
It is thus proposed according to the invention to design the navigation system in such a way that the data are arranged in two different databases, in fact in such a way that only geographical regions in the form of a list are stored in the first database, whereas the unique, specific street names and/or special destinations are stored in the second database, in each case with a reference to at least one geographical region to which the respective street or the respective special destination geographically belongs. By use of a data structure of this type, an search index is produced on the whole in which the respective database can be searched via a linear search so that the search for the possible destinations can be carried out with a runtime complexity of O(n). On the one hand, the time requirement compared with other database structures is significantly reduced; on the other hand, the size of the two databases is also relatively small. Accordingly, no large main memory is required in the motor vehicle.
On the one hand, a first results list of database entries from the first database and, on the other hand, a second results list of database entries from the second database are therefore generated by the processing device depending on the search input. The found street names and/or special destinations are then matched with the found geographical regions using the respective references. If it is established here that the reference of a found street and/or special destination refers to a region which is not contained in the results list, these database entries can be discarded.
The method according to the invention can be explained using the following example: The two terms “München Hanau” [“Munich Hanau”] are entered by the user as a search input. The processing device then searches the first database and finds both the town “München” and the town “Hanau” as geographical regions. The first results list thus contains the two towns: “München” and “Hanau”. The processing device also searches the second database and finds “Münchener Strasse” and “Hanauer Strasse” there. The second results list therefore contains the two streets: “Münchener Strasse” and “Hanauer Strasse”. In an allocation, the processing device establishes that in the case of “Hanauer Strasse”, a reference is given to the town “München”, whereas no such reference to the town “Hanau” is given in the case of “Münchener Strasse”. The only possible entry pair from these two results lists is therefore: “Hanauer Strasse in München”. This destination is then displayed on the display device.
The database entries of the second database can, in each case, additionally contain a reference to a navigation map in order to then be able ultimately to resolve individual destinations geographically. Alternatively, the database entries of the second database can also be referenced from the navigation map, provided that the data format of the navigation map permits or provides this.
In one embodiment, it is provided that the database entries, i.e. the street names and/or special destinations, are stored in alphabetical order in the second database. The time required for the search can thus be reduced to a minimum in the case of a linear search.
It proves to be advantageous if the geographical regions indicated in the first database are arranged hierarchically into at least two hierarchy levels so that, for each region of a specific hierarchy level, a plurality of regions belonging geographically to this region are allocated to a hierarchy level subordinated thereto. The hierarchical structure may, for example, be formed according to a national administrative division which designates the vertical administrative structures existing in each case in the different countries. A total of ten different hierarchy levels, for example, can be provided. A first hierarchy level, a main level, may, for example, contain the countries, i.e., for example, “Germany”, “France”, “Austria” and the like. The countries may in turn be subdivided into federal provinces, which then form a second hierarchy level. The federal provinces can then contain the respective further administrative units as a third hierarchy level, and so on.
In terms of the required search time, it has proven to be advantageous if the geographical regions indicated in the first database are stored in a tree structure in such a sequence that a specific region is immediately followed by all subordinated regions belonging to this region. In this way, the regions subordinated to a specific region can be found particularly quickly in the database. The regions within the same hierarchy level are preferably arranged in alphabetical order.
If a region from a specific hierarchy level is found depending on the search input of the user, all regions subordinated to this region are preferably additionally included in the first results list. If, for example, the region “Bad Tölz” is found using the search input, the subordinated regions “Bad Tölz Center”, “Bad Tölz South” and “Bad Tölz East” are also included in the first results list. In this way, a very precise and simple allocation of the found street names and/or special destinations to the corresponding region is enabled. For example, it can also be provided that the specified references that are indicated in the second database refer to the smallest region, i.e. to the region from the last hierarchy level, in which the respective street and/or the respective special destination is located.
Additionally or alternatively, if a specific region and a region subordinated to it are found depending on the search input, it can also be provided that only the subordinated region is included in the first results list. The processing time in the search is thus furthermore reduced. If, for example, the search input “Bad Tölz Center” is received, only the region “Bad Tölz Center” is included in the first results list, but not the higher-order region “Bad Tölz”.
In one preferred embodiment, the first and/or the second database is/are stored in a data memory in compressed, in particular delta-compressed, form. The required memory space is thus reduced to a minimum. This embodiment proves to be particularly advantageous, particularly in relation to the second database in which the street names and/or the special destinations are stored. The second database contains significantly more database entries than the first database, so that a large amount of memory space is saved on the whole through the compression of the second database. A delta compression may, for example, appear such that, for each database entry, a number is initially defined which indicates how many initial letters from the immediately preceding database entry are to be accepted. If, for example, the following two database entries “Aachener Strasse” and “Aachener Weg” are stored in compressed form, the second database entry can consequently be stored: “9 Weg”. This means that the first nine letters of the second database entry are accepted from the preceding entry.
It can be provided that the first and/or the second database is/are subdivided into a plurality of subdatabases in which a subset of the database entries is, in each case, stored. Each subdatabase can be provided in each case in the form of a separate file which is stored in a data memory. The subdivision of the first and/or second database into a plurality of subdatabases offers the advantage that the processing device can load the individual subdatabases dynamically during the performance of the search, so that an improved storage utilization is achieved overall. A smaller main memory is therefore also required, and the search time is furthermore reduced. The provision of a plurality of subdatabases also has advantages in terms of updating the database. Only partial updates can be carried out, so that the entire database does not need to be updated. The subdivision into a plurality of subdatabases may be undertaken, for example, for larger geographical areas, such as, for example, for the USA.
If one of the databases is subdivided into a plurality of subdatabases, the processing device can load or copy at least one of the subdatabases from a non-volatile memory in which the first and the second database are stored into a volatile main memory during the search for the possible destinations, and can then search for the matching database entries in the subdatabase of the main memory. For example, the subdatabases can be loaded and searched one after another or temporally in parallel. However, with a specific search input, not all subdatabases need to be searched, but only those which are assessed as plausible for the received search input. This embodiment generally ensures a further acceleration of the search.
As already explained, the search of the first and/or the second database can be carried out by means of a linear search, in particular with a skip function. With a skip function, individual entries in the list can be passed over. This also reduces the search time.
The selection list is preferably generated in real time: In one embodiment, if the search input is continuously edited or completed in an input field by the user, it is provided that, a previously performed partial input is already repeatedly received in each case by the processing device during the search input and the selection list is continuously updated depending on the respective current partial input. In particular, the selection list can be updated after each new character or each new search term of the search input depending on the respective current partial input. The user thus receives the possible destinations displayed in the selection list without having to complete or confirm the search input. If the found possible destinations are prioritized accordingly, it may even be possible for the required destination to be displayed already following the input of a few characters, so that the effort required by the user in searching for his required destination is minimal.
It is preferred if a priority value is assigned in each case to the possible destinations that are found by the processing device and displayed in the selection list. The sequence of the possible destinations in the selection list can then be determined depending on the priority values. In this way, it is possible to display the possible destinations that currently appear to be more plausible than other destinations in foremost position in the selection list. A procedure of this type is particularly user-friendly, since the user first receives the plausible destinations displayed and can quickly find his required destination accordingly.
In terms of the prioritization of the found destinations, it has furthermore proven to be advantageous if the aforementioned priority values are determined depending on at least one of the following parameters.
In one embodiment, the priority values can be determined depending on a frequency with which the respective destination has previously been selected for the calculation of a navigation route by the user. If one specific destination has been more frequently selected than other destinations, this destination can be displayed further in front in the selection list than the other destinations, so that the user can find this popular destination without much effort and can quickly enter it.
Additionally or alternatively, the priority values can be determined depending on a current position of the motor vehicle. The current geographical position of the motor vehicle represents a parameter which plays a certain role in the assessment of the plausibility of the found destinations.
The priority values may, for example, be determined depending on a distance to the respective destination from the current geographical position of the motor vehicle. For example, those destinations which are closer to the current position of the motor vehicle can be displayed higher in the selection list than the other destinations. This embodiment exploits the fact that the destinations which are located at a relatively great distance from the motor vehicle are selected on the whole less frequently than the closer destinations.
Furthermore additionally or alternatively, it can be provided that the priority values are determined depending on a degree of correspondence between the respective destination and the search input of the user. Here, the relationship may apply that the greater the degree of correspondence, the higher the respective destinations are displayed in the selection list.
The priority values can additionally or alternatively also be determined depending on a type, in particular an administrative type and/or the category (e.g. POI) of the respective destination. Thus, for example, towns or smaller regions can be prioritized differently from streets or special destinations. For example, it may be that the more precise and unambiguous the destination is, the higher this destination is displayed in the selection list.
If a town is found as a possible destination, the priority value may also be determined depending on a number of inhabitants of the town.
The aforementioned parameters may be taken into account in determining the priority values, for example with a predefined weighting.
The user may also be offered the facility to include the displayed possible destinations individually in a favorites list. In a subsequent later search, those destinations which are included in the favorites list can then be placed in foremost position.
If the search input includes a plurality of search terms (referred to as “tokens”) which are entered separated from one another by a blank space or other separating character, the processing device can search the two databases independently from the sequence of the input of the search terms. The search input “München Hanauer Strasse 46” therefore leads overall to the same selection list as, for example, the search input “Hanauer Strasse 46 München” or “46 Hanauer Strasse München”. Street names which start with a number, for example “50th Avenue” are preferably also supported. These street names can also be indicated at any position in the search input.
The processing device preferably supports incomplete and/or incorrect search inputs also. Such a situation may arise, for example, if the search term “Munch” or “Munchen” is entered instead of “München”. The processing device can determine a degree of similarity between the entered search terms and the stored database entries and can compare this degree of similarity with a predefined threshold. If the degree of similarity exceeds this threshold, the found database entry is selected.
If a plurality of search terms are entered, the processing device can optionally also combine specific search terms. For example, this can be carried out if the terms “Hanauer Strasse” are entered in the search. These two search terms can be combined so that a search is carried out in the databases for “Hanauer Strasse”.
On the whole, the method according to the invention enables a flexible and complete search for possible destinations with a runtime complexity of O(n). The search results are evaluated on the basis of different parameters and are finally provided in a selection list sorted according to the user context. The method is based on an improved data format for the search index which is divided into two different databases or tables: on the one hand, the geographical regions (“Area Hierarchy”) and, on the other hand, the street names and/or special destinations (“Streets/POI Hierarchy”). The databases are created for the search index, for static data, in particular in a compilation step in the manufacture/programming of the navigation system. For dynamic changes to the output data, such as, for example, the contact data defined by the user himself, parts of the search index are recompiled in the operation of the motor vehicle and are adapted accordingly. The decisive advantage of the method lies, in particular, in the processing of the databases and in the data format for the search index. On the one hand, the first and/or the second database is stored in highly compressed form in order to occupy the smallest possible amount of memory space in the motor vehicle; on the other hand, the search index is created as completely as possible for all relevant destinations (addresses, POIs, contacts, etc.) and is optimized for fast queries during the search. In particular, memory space can be saved by use of this data format. The larger second database thus requires only 8 MB for all street names and special destinations in Germany, whereas some 300 MB would be required for the same information in the NDS Free Text Search Building Block.
The invention furthermore relates to a motor vehicle, in particular an automobile, with a navigation system that is designed to carry out a method according to the invention. The preferred embodiments presented in relation to the method according to the invention and their advantages apply accordingly to the motor vehicle according to the invention.
Other objects, advantages and novel features of the present invention will become apparent from the following detailed description of one or more preferred embodiments when considered in conjunction with the accompanying drawings.